package com.zxy.javaarithmetic.chapter_2_LinkList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_5_ReversePartLinkList
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/10 11:45
 *  @描述：    反转部分单向链表
 */
public class P_5_ReversePartLinkList {

	public static void main(String[] args) {

		Node head = LinkListUtils.getNode(5);
		LinkListUtils.printNode(head);

		LinkListUtils.printNode(reversePartLinkedList2(head, 2, 4));
	}

	private static Node reversePartLinkedList2(Node head, int from, int to) {
		if (head == null || from < 1 || from > to) return head;

		Node fPre = null;
		Node toPos = null;
		Node node1 = head;
		int len = 0;
		while (node1 != null) {
			len++;
			fPre = len == from - 1 ? node1 : fPre;
			toPos = len == to + 1 ? node1 : toPos;
			node1 = node1.next;
		}
		if (to > len) {
			return head;
		}

		node1 = fPre == null ? head : fPre.next;
		Node node2 = node1.next;
		node1.next = toPos;
		Node temp = null;
		while (node2 != toPos) {
			temp = node2.next;
			node2.next = node1;
			node1 = node2;
			node2 = temp;
		}
		if(fPre != null){
			fPre.next = node1;
			return head;
		}
		return node1;
	}

	private static Node reversePartLinkedList(Node head, int from, int to) {
		if (head == null || from < 1 || from > to) return head;
		int length = 1;
		Node cur = head;
		while (cur.next != null) {
			length++;
			cur = cur.next;
		}
		if (to <= length) {
			Node startPreNode = null;
			Node pre = null;
			cur = head;

			int n = 0;
			while (cur != null) {
				n++;
				if ((n + 1) == from) {
					startPreNode = cur;
				}
				if (n > from && n < to) {
					Node next = cur.next;
					cur.next = pre;
					pre = cur;
					cur = next;
				} else if (n == to) {
					Node next = cur.next;
					cur.next = pre;
					if (startPreNode == null) {
						head.next = next;
						head = cur;
					} else {
						startPreNode.next.next = next;
						startPreNode.next = cur;
					}
					break;
				} else {
					pre = cur;
					cur = cur.next;
				}
			}
		}

		return head;
	}
}
